#include "./head.h"
int main()
{
	int i;
	srand(time(NULL));
	//int* arr = (int*)calloc(SIZE, sizeof(int));
	int arr[SIZE];
	for (i = 0; i < SIZE; ++i)
	{
		arr[i] = rand() % MAX;//random产生随机数
	}
	printf("Rand success!\n");
	printf("Initial arangement of a is :\n");
	for (i = 0; i < SIZE; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	time_t beg = time(NULL);
	//bubblesort(arr);
	//selectsort(arr);
	//insertsort(arr);
	//shellsort(arr);
	//quicksort(arr, 0, SIZE - 1);
	//insertSort2(arr);
	//shellSort2(arr);
	//quickSort2(arr, 0, SIZE - 1);
	//heapsort(arr, SIZE);
	//mergesort(arr, 0, SIZE - 1);
	countsort(arr);
	time_t end = time(NULL);
	printf("Time taking = %d secs\n", end - beg);
	printf("After sort :\n");
	for (i = 0; i < SIZE; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void bubblesort(int* a)
{
	int i, j;
	int flag;//标记一轮是否发生交换
	for (i = SIZE - 1; i > 0; --i)
	{
		flag = 0;
		for (j = 0; j < i; ++j)
		{
			if (a[j] > a[j + 1])
			{
				SWAP(a[j], a[j + 1]);
				flag = 1;
			}
		}
		if (!flag)
		{
			return;
		}
	}
}
void selectsort(int* a)
{
	int i, j;
	int min;//记录当前循环的遍历到的最小值的下标
	for (i = 0; i < SIZE; ++i)
	{
		min = i;
		for (j = i; j < SIZE; ++j)
		{
			if (a[min] > a[j])
			{
				min = j;
			}
		}
		SWAP(a[min], a[i]);
	}
}
void insertsort(int* a)
{
	int i, j;
	for (i = 1; i < SIZE; ++i)
	{
		for (j = i; j > 0; --j)
		{
			if (a[j] < a[j - 1])
			{
				SWAP(a[j], a[j - 1]);
			}
			else
			{
				break;
			}
		}
	}
}
void insertSort2(int* arr)
{
	for (int i = 1; i < SIZE; ++i)
	{
		int toInsert = arr[i];
		int j;
		for (j = i - 1; j >= 0 && arr[j] > toInsert; --j)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = toInsert;
	}
}
void shellsort(int* a)
{
	int toinsert;
	int i = 0, j, k;
	for (int gap = SIZE >> 1; gap >= 1; gap >>= 1)//缩小增量
	{
		for (i = 0; i < gap; ++i)//一个增量对应的所有排序
		{
			for (j = i + gap; j < SIZE; j += gap)//一次插入排序
			{
				toinsert = a[j];
				for (k = j - gap; k >= 0; k -= gap)
				{
					if (a[k] > toinsert)
					{
						a[k + gap] = a[k];
					}
					else
					{
						break;
					}
				}
				a[k + gap] = toinsert;
			}
		}
	}
}
void shellSort2(int* arr)//希尔排序每次缩小增量都会使数组变得更有序
{
	for (int gap = SIZE >> 1; gap >= 1; gap >>= 1)
	{
		for (int i = gap; i < SIZE; i += gap)
		{
			int toInsert = arr[i];
			int j;
			for (j = i - gap; j >= 0 && arr[j] > toInsert; j = j - gap)
			{
				arr[j + gap] = arr[j];
			}
			arr[j + gap] = toInsert;
		}
	}
}
void quicksort(int* a, int m, int n)
{
	if (m < n)
	{
		int i = m, j = n;
		int pivot = a[i];
		int p = i;//分割下标
		while (i < j)
		{
			while (a[j] > pivot&& i < j)
			{
				--j;
			}
			if (i < j)
			{
				p = j;
				a[i] = a[j];
				++i;
			}
			while (a[i] < pivot && i < j)
			{
				++i;
			}
			if (i < j)
			{
				p = i;
				a[j] = a[i];
				--j;
			}
		}
		a[p] = pivot;
		quicksort(a, m, p - 1);
		quicksort(a, p + 1, n);
	}
}
int divide(int* arr, int beg, int end)
{
	if (beg < end)
	{
		int tmp = arr[end];
		int j = beg;
		for (int i = beg; i < end; ++i)
		{
			if (arr[i] < tmp)
			{
				SWAP(arr[j], arr[i]);
				++j;
			}
		}
		SWAP(arr[j], arr[end]);
		return j;
	}
}
void quickSort2(int* arr, int beg, int end)
{
	if (beg < end)
	{
		int ret = divide(arr, beg, end);
		quickSort2(arr, beg, ret - 1);
		quickSort2(arr, ret + 1, end);
	}
}
void adjustMaxheap(int* arr, int pos, int size)
{
	int dad = pos;
	int son = 2 * dad + 1;
	while (son < size)
	{
		if (arr[son] < arr[son + 1] && son + 1 < size)
		{
			son += 1;
		}
		/*if (arr[son] > arr[dad])
		{
			SWAP(arr[son], arr[dad]);
		}
		dad = son;
		son = 2 * dad + 1;*/
		if (arr[son] > arr[dad])
		{
			SWAP(arr[son], arr[dad]);
			dad = son;
			son = 2 * dad + 1;
		}
		else
		{
			break;//因只需局部调整，故若根节点大于其所有子节点，可以立即跳出循环
		}

	}
}
void heapsort(int* arr, int size)
{
	int i;
	for (i = size / 2 - 1; i >= 0; --i)//i>0***
	{
		adjustMaxheap(arr, i, size);
	}
	for (i = size - 1; i > 0; --i)
	{
		SWAP(arr[i], arr[0]);
		adjustMaxheap(arr, 0, i);
	}
}
void merge(int* arr, int low,int mid, int high)
{
	int a[SIZE];
	int i,j,k;
	for (i = low; i <= high; ++i)
	{
		a[i] = arr[i];
	}
	i = low;
	j = mid + 1;
	k = low;
	while (i <= mid && j <= high)
	{
		if (a[i] < a[j])
		{
			arr[k++] = a[i++];
		}
		else if(a[i]>a[j])
		{
			arr[k++] = a[j++];
		}
		else
		{
			arr[k++] = a[i++];
		}
	}
	if (i <= mid)
	{
		while (i <= mid)
		{
			arr[k++] = a[i++];
		}
	}
	else
	{
		while (j <= high)
		{
			arr[k++] = a[j++];
		}
	}
}
void mergesort(int* arr, int low, int high)
{
	
	if (low < high)
	{
		int mid = (low + high) / 2;
		mergesort(arr, low, mid);
		mergesort(arr, mid + 1, high);
		merge(arr, low, mid, high);
	}
}
void countsort(int* a)
{
	int count[MAX] = { 0 };//用于计数
	int i,j,k=0;
	for (i = 0; i < N; ++i)
	{
		count[a[i]]++;
	}
	for (i = 0; i < MAX; ++i)
	{
		for (j = 0; j < count[i]; ++j)
		{
			a[k++] = i;
		}
	}
}